/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-05 21:38:37
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-06 15:25:06
 * @FilePath: \LeetCode\39.组合总和.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=39 lang=cpp
 *
 * [39] 组合总和
 * 
 * 方法1：优化子集树顺序选择子结点
 */

#include <vector>
#include <algorithm>
#include <iostream>

// @lc code=start
class Solution
{
public:
    std::vector<std::vector<int>> result;
    std::vector<int> v_selected; // 记录选择数字
    int sum = 0;               // 组合总和
    int len = 0;               // candidates.length
    int m_target = 0;

    void visitSubTree(const std::vector<int> &candidates, int i)
    {
        if (sum == m_target)
        {
            result.push_back(v_selected);
            return;
        }

        /* 顺序访问后续结点 */
        for (int k = i; k < len; k++)
        {
            int current = candidates[k];
            /* 剪枝优化 candidates单调递增 */
            if (sum + current > m_target)
                continue;
            sum += current;
            v_selected.push_back(current);
            visitSubTree(candidates, k); // 重复选择当前结点
            sum -= current;
            v_selected.pop_back();
        }
    }

    std::vector<std::vector<int>> combinationSum(std::vector<int> &candidates, int target)
    {
        len = candidates.size();
        m_target = target;

        visitSubTree(candidates, 0);

        return result;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> candidates = {2, 3, 5};

    std::vector<std::vector<int>> result = solution.combinationSum(candidates, 8);
    for (auto v : result)
    {
        for (auto n : v)
            std::cout << n << " ";
        std::cout << std::endl;
    }

    return 0;
}